package org.chnxi.study.datastructrues.stack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * 使用逆波兰表达式（后缀匹配）进行计算
 * 缺少，小数位，空格等干扰字符，数字是负数
 */
public class PolandNotationCalculator {

    public static void main(String[] args) {

        String str = "1+((2+3)*4)-5";
        List<String> infixExprList = toInfixExpression(str);
        System.out.println(infixExprList);

        List<String> suffixExprList = parseSuffixExpressionList(toInfixExpression(str));
        System.out.println(suffixExprList);

        int result = calculator(suffixExprList);

        System.out.println(str + "=" + result);

        //(3+4)*5-6
//        String expression = "3 4 + 5 * 6 -";
//
//        ArrayList<String> list = getListString(expression);
//
//        int result = calculator(list);
//
//        System.out.println(expression+"="+result);
    }

    public static ArrayList<String> getListString(String suffixExpression){
        String[] split = suffixExpression.split(" ");
        ArrayList<String> result = new ArrayList<>();
        for(String str : split){
            result.add(str);
        }
        return result;
    }

    /**
     * 使用后缀表达式进行计算
     * @param ls
     * @return
     */
    public static int calculator(List<String> ls){
        Stack<String> stack = new Stack<String>();
        for (String item : ls){
            //使用正则判断数字
            if(item.matches("\\d+")){ // 如果是数字直接入栈
                stack.push(item);
            }else{  //运算符，pop出两个数，进行运算
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int result = 0;
                if(item.equals("+")){
                    result = num1 + num2;
                }else if(item.equals("-")){
                    result = num1 - num2;
                }else if(item.equals("*")){
                    result = num1 * num2;
                }else if(item.equals("/")){
                    result = num1 / num2;
                }else{
                    throw new RuntimeException("表达式错误");
                }
                stack.push(result+"");
            }
        }
        //最后留在stack中的数值是运算结果；
        return Integer.parseInt(stack.pop());
    }

    /**
     * 将中缀表达式转换为后缀表达式
     * 1、先将中缀表达式转为list
     * @param ls
     * @return
     */
    public static List<String> parseSuffixExpressionList(List<String> ls){
        //定义两个栈
        Stack<String> stack1 = new Stack<>();
        //说明：在过程中stack2没有pop的操作，最终还需要逆序，此处使用list来代替
        List<String> list = new ArrayList<>();

        for (String item : ls){
            //如果一个数，加入到list
            if(item.matches("\\d+")){
                list.add(item);
            }else if(item.equals("(")){ //如果是左括号"("，则直接压入stack1
                stack1.push(item);
            }else if(item.equals(")")){ //如果是右括号")"，则依次弹出stack1栈顶的运算符，并压入stack2，直到遇到左括号为止，此时将这一对括号丢弃
                while(!stack1.peek().equals("(")){
                    list.add(stack1.pop());
                }
                stack1.pop();//将左括号弹出移除
            }else{
                //当item的优先级小于或等于stack1栈顶运算符，将stack1的运算符弹出加入list
                while(stack1.size() != 0 &&
                        Operation.getVal(stack1.peek()) >= Operation.getVal(item)){
                    list.add(stack1.pop());
                }
                //将item压入stack
                stack1.push(item);
            }
        }

        //将stack中剩余的运算加入到list中
        while (stack1.size() != 0){
            list.add(stack1.pop());
        }

        return list;
    }

    /**
     * 讲中缀表达式转换为list
     * @param suffixExpression
     * @return
     */
    public static List<String> toInfixExpression(String suffixExpression){
        List<String> ls = new ArrayList<>();

        int i = 0; //定义指针，用于遍历中缀表达式字符串
        String str; //做多位数拼接
        char c; //遍历到一个字符放到c

        do{
            //如果c是非数字，直接加到ls中去
            c = suffixExpression.charAt(i);
            if(c < 48 || c > 57){
                ls.add("" + c);
                i++; //i需要后移
            }else{
                //需要考虑多位数的问题
                str = ""; //先清除str中的内容

                while(i < suffixExpression.length() &&
                        (c = suffixExpression.charAt(i)) >= 48 &&
                        (c = suffixExpression.charAt(i)) <= 57){
                    str += c; //拼接多位数
                    i++;
                }
                ls.add(str);
            }
        }while(i<suffixExpression.length());
        return ls;
    }

}

class Operation{
    private static  int add = 1;
    private static int sub = 1;
    private static int mul = 2;
    private static int div = 2;

    public static int getVal(String operation){
        int result = 0;
        switch (operation){
            case "+":
                result = add;
                break;
            case "-":
                result = sub;
                break;
            case "*":
                result = mul;
                break;
            case "/":
                result = div;
                break;
            default:
                //throw new RuntimeException("错误的运算符");
        }
        return result;
    }
}